#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

bool ispos(int arr[],int sub,int value)
{
	return arr[sub]<=value&&arr[sub+1]>=value;
}

int binarySearch(int arr[],int low,int high,int value) //查找插入位置的下标 
{
	int mid=low+(high-low)/2;
    if(ispos(arr,mid,value))
        return mid+1;
    if(arr[mid]>value)
        return binarySearch(arr,low,mid-1,value);
    if(arr[mid]<value)
        return binarySearch(arr,mid+1,high,value);
}

void insert(int arr[],int sub,int size,int value)
{
	for(int i=size-1;i>=sub;i--) //挨个往后挪，这完全就是个沙雕操作 
		arr[i+1]=arr[i];
	arr[sub]=value;
}

int main()
{
	printf("按从小到大顺序定义你的数组，over结束：\n");
	string shuru;
	int arr[100];
	int size=0;
	for(int i=0;i<100;i++)
	{
		cin>>shuru;
		if(shuru=="over")
			break;
		else
		{
			arr[size]=atoi(shuru.c_str());
			size++;
		}
	}
	
	int value;
	printf("你要插入的数是：");
	scanf("%d",&value);
	printf("\n");
	//实际代码就这两句 
	int sub=binarySearch(arr,0,size-1,value);
	insert(arr,sub,size,value);
	
	for(int i=0;i<size+1;i++)
		printf("%d ",arr[i]);
}